﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace 递归算法
{
    class recursive_algorithm
    {
        /// <summary>
        /// 递归 求斐波那契数列，时间复杂度为n的指数级别
        /// </summary>
        /// <param name="n">斐波那契数列项数</param>
        /// <returns>第N项的值</returns>
        static Int64 Fib(Int32 n)
        {
            return n <= 2 ? (n <= 1 ? 1 : 2) : Fib(n - 2) + Fib(n - 1);
        }

        /// <summary>
        /// 非递 归算法，动态规划思路，保存前一个值
        /// </summary>
        /// <param name="n">斐波那契数列项数</param>
        /// <returns>第N项的值</returns>
        static Int64 UnFib(Int32 n)
        {

            if (n <= 2)
            {
                return n <= 1 ? 1 : 2;
            }
            else
            {
                List<Int64> list = new List<Int64>();
                list.Insert(0, 0);
                list.Insert(1, 1);
                list.Insert(2, 1);
                Enumerable.Range(3, n).ToList().ForEach(index =>
                {
                    list.Insert(index, list[index - 1] + list[index - 2]);
                });
                return list[list.Where(p => p != 0).Count() - 1];
            }
        }


        static void Main(string[] args)
        {

            Stopwatch watch = new Stopwatch();
            watch.Start();
            Int64 num = 0;
            Enumerable.Range(1, 70).ToList().ForEach(item =>
            {
               // num = Fib(item);
                num = UnFib(item);
                Console.Write("{0}:{1}\t", item, num);
                if (item % 5 == 0)
                {
                    Console.WriteLine();
                }
            }
            );
            watch.Stop();
            Console.WriteLine("\n测试用时:{0}(毫秒)\t\t数值是:{1}\t\t", watch.Elapsed.Ticks.ToString(), num.ToString());
            Console.ReadKey();
        }


    }
}
